//高级搜索算法介绍
//advanced_search_algorithm_introduction.cpp

//为了找出地球上最高的山，一群有志气的兔子们开始想办法

//1)分支界定法(Branch and Bound)
//分支界定法是排除根据已知条件可以判断一个搜索子空间中必然没有目标最优解的方法
//当搜索至某一个子空间，若根据当前条件可以判断出该子空间的某个分支中不可能存在最优解
//则可以直接跳过对该分支的搜索，从而节省时间
//该算法总是伴随着大量的剪枝，流行的方法是用队列广度优先或评价函数来实现
//
//2)局部搜索(Local Search)
//局部搜索是一类启发式搜索算法
//它从一个初始方案开始重复以下步骤：
//通过一个动作产生邻居方案，所有邻居方案的集合称为一个邻域
//按照一种评价标准，选择邻域中的最优方案，继续产生下一轮的邻居方案
//直到到达结束条件为止
//算法的关键在于产生邻居方案的动作以及选择邻居方案的评价标准
//
//局部搜索中流行的算法有：
//简单局部搜索(Simple Local Search，也称爬山法，Hill Climbing)
//模拟退火(Simulated Annealing)
//禁忌搜索(Tabu Search)
//
//简单局部搜索，爬山法：
//简单的选择当前邻域中的最优方案，直到无法找到比自己更好地方案
//但无法保证局部最优是全局最优
//模拟退火：
//通过设置一个温度来防止算法陷入局部最优，初始化时设置一个高温，重复以下步骤：
//在当前邻域中随机选择一个方案，若该方案比当前方案好则将当前方案替换为该方案
//若该方案比当前方案差，则按照一个概率来接受该方案，然后更新温度
//这个概率是关于两方案的评价值以及温度的函数，且随着温度的减小概率也减小
//即随着迭代的进行，温度下降，越来越不能接受比当前方案小的邻居方案
//禁忌搜索：
//该算法通过设置禁忌表，禁忌长度和解禁条件，避免了短时间内的重复搜索
//其中禁忌表记录了一些邻居方案的属性，凡拥有这个属性的邻居方案都不予考虑
//禁忌表中的每个被记录的属性都有一个禁忌长度，在该长度内的邻居方案不予考虑
//解禁条件：当含有禁忌属性的邻居方案比历史上最优的方案还有好时
//选择这个被禁忌的方案，其他情况下不考虑被禁忌的方案
//禁忌长度可以是一个定值，也可以是动态变化的
//
//3)遗传算法
//借鉴生物进化学中种群遗传，突变，自然选择以及杂交等现象的一种进化算法
//将初始方案看作一个个体，重复以下步骤：
//每次的迭代都保留一组候选个体，按照某种适应函数在候选个体中选取较优秀的个体
//再用遗传算子(选择，交叉和突变)对这些个体进行组合，产生新一代候选个体
//直到达到终止条件
//
//本文引用了“局部搜索算法”，作者“JiePro”
//“经典算法研究系列：七，深入浅出遗传算法”，作者“v_JULY_v”
